Computing devices continue to become more ubiquitous to daily life. Such devices take the form of computer desktops, laptops, tablet PCs, e-book readers, interactive whiteboards, mobile phones, smartphones, wearable computers, global positioning system (GPS) units, enterprise digital assistants (EDAs), personal digital assistants (PDAs), game consoles, and the like. Further, computing devices are being incorporated into cars, trucks, farm equipment, manufacturing equipment, building environment control (e.g., lighting, HVAC), and home and commercial appliances.
Computing devices generally consist of at least one processing element, such as a central processing unit (CPU), some form of memory, and input and output devices. The numerous varieties of computing devices as well as their subsequent uses necessitate a variety of input devices. One type of input device is a touch sensitive surface such as a touch screen or touch pad wherein user input is received through contact between the user's finger or an instrument such as a pen or stylus and the touch sensitive surface. Another type of input device is an input surface that senses motions made by a user above the input surface and without touching the input surface. Either of these methods of input can be used generally for drawing or inputting shapes. When the user input is a shape, the computing device must interpret the user's natural drawing technique using, for example, an on-line geometric shape recognition system or method.
Generally, on-line geometric shape recognition systems or methods monitor the initiation of a stroke, such as when the user contacts a touch sensitive surface (pen-down); the termination of a stroke, such as when the user stops contacting a touch sensitive surface (pen-up); and any movements (i.e. the stroke) the user makes with his or her finger or pen between the initiation and termination of the stroke.
On-line geometric shape recognition systems or methods may be classified as single-stroke or multi-stroke. Single-stroke recognition analyzes each single-stroke as a separate primitive. A primitive is a geometric shape. The system may only utilize single-stroke primitives or may utilize shorthand for primitives that would otherwise require multiple strokes. These single-stroke systems or methods typically have less input errors but may require users to memorize stroke patterns for multi-stroke primitives if shorthand is utilized. Multi-stroke recognition systems can recognize natural drawing and are more intuitive to users because one does not have to learn shorthand.
Whether one uses a single or multi-stroke system, on-line geometric shape recognition systems or methods usually consist of preprocessing, primitive recognition, and constraint solving. In practice, on-line geometric shape recognition systems or methods may include these steps along with additional steps. Further, on-line geometric shape recognition systems or methods may not clearly delineate each step or may perform the steps in an alternate order.
Preprocessing typically includes discarding irrelevant input data and normalizing, sampling, and removing noise from relevant data.
Primitive recognition specifies the different ways to break down the input data into individual lines, shapes, or other segments based on a set of basic models (e.g., lines, circles, ellipses, arcs, and points). Primitive recognition generally associates the segments with possible primitive candidates. Primitives can be any type of shape or curve, from basic (e.g., line segment, circle, ellipse, arc of circle, arc of ellipse, and point) to more complex (e.g., sinusoidal, spline, Bezier, and parametric function plots). Primitive candidates can comprise single-stroke, multi-stroke, and/or geometric variations of shapes. Primitive recognition may also be preceded by gesture determination that determines whether the input data is geometric shape or a gesture (e.g., an input stroke that provides additional information as to the relation of already input geometric shapes).
Constraint solving generally includes checking the primitives against a set of constraints (e.g., length equality, angle equality, parallelism, symmetry, alignment, tangency, connection, and perpendicularity). Typically, constraints are defined on a primitive level, meaning they are associated with specific primitives. Constraints can be implicit or explicit. Implicit constraints are such that the system infers a constraint based on user input of primitives. For example, the system or method may detect that two lines are close enough to being perpendicular and infer that a perpendicular restraint should apply, outputting two perpendicular lines. In this example, perpendicularity is an example of an implicit constraint. Explicit constraints are such that the user explicitly specifies additional constraints to apply. For instance, the system or method may not detect that two lines were intended to be perpendicular. A user may input an additional gesture to provide this explicit constraint. An on-line geometric shape recognition system or method may recognize both implicit and explicit constraints. Once the set of primitives and set of constraints are built, a constraint solving method enforces the maximum number of possible constraints. Following constraint solving, the on-line geometric shape recognition system or method outputs smooth geometric shapes.
Constraint solving at the primitive level is usually limited in the number of primitives and constraints that a system can analyze because constraints are generally defined at the primitive level and closely linked to primitive types. Each new primitive or constraint introduced into the system causes exponentially more relationships between primitives and constraints, creating exponentially more possibilities to analyze during constraint solving.
The present system and method provides improved results for user input recognition by defining the constraints at a vector component level rather than primitive level. By defining constraints on the vector component level, the system and method is able to better handle increasingly large sets of primitives and constraints.